package www.study.com;

//两数相除 https://leetcode.cn/problems/divide-two-integers/
public class code28 {
    public static void main(String[] args) {

    }

    class Solution {
        public int divide(int dividend, int divisor) { //dividend / divisor
            if(divisor == 0 || dividend == 0) return 0; //考虑除数为0
            //考虑边界
            if(dividend == Integer.MIN_VALUE){
                if(divisor == 1) return Integer.MIN_VALUE;
                if(divisor == -1) return Integer.MAX_VALUE;
            }
            if(divisor == Integer.MIN_VALUE){
                return dividend == Integer.MIN_VALUE ? 1 : 0;
            }
            if(dividend == Integer.MAX_VALUE && divisor == 1){
                return Integer.MAX_VALUE;
            }
            if(dividend == Integer.MAX_VALUE && divisor == -1){
                return -Integer.MAX_VALUE;
            }
            //考虑正负号
            boolean flag = (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) ? true : false;//符号位 false代表正数，true代表负数
            dividend = -Math.abs(dividend); //Math.abs(dividend);
            divisor = -Math.abs(divisor); //Math.abs(divisor);
            int l = 0,r = Integer.MAX_VALUE; //边界注意要取正
            int res = -1;
            while(l <= r){ //注意是小于等于，否则会有遗漏
                //int mid = (l + r) >> 1;
                int mid = l + ((r - l) >> 1); //注意：不可以写成int mid = l + (r - l) >> 1
                //System.out.println(res);
                if(quickMul2(divisor,mid,dividend)){
                    res = mid;
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            return flag ? -res : res;
        }
        //a负数，b为正数
        public boolean quickMul2(int a,int b,int range){ //a * b
            int base = a;
            int res = 0;
            while(b != 0){
                if((b & 1) == 1){
                    if(res < range - base) return false;
                    res += base;
                    //if(res > range) return false;
                }
                if(b != 1 && base < range - base) return false;
                base += base;
                b >>>= 1;
            }
            //System.out.println(res);
            return true;
        }
        //缺点：求得是 除数*商，如果被除数是Integer类型的最小值，导致除数*商越界
        public boolean quickMul(int a,int b,int range){ //a * b
            int base = a;
            int res = 0;
            while(b > 0){
                if((b & 1) == 1){
                    if(res > range - base) return false; //要加上，防止超时，不能写成res+base>range，可能会越界
                    res += base;
                    //if(res > range) return false;
                }
                if(b != 1 && base > range - base) return false; //要加上，防止超时
                base += base;
                b >>>= 1;
            }
            //System.out.println(res);
            return res <= range;
        }
    }
}
